Content addressable memory (CAM) devices are frequently used in network switching and routing applications to determine forwarding destinations for data packets, and are also used to provide more advanced network Quality of Service (QoS) functions such as traffic shaping, traffic policing, rate limiting, and so on. More recently, CAM devices have been deployed in network environments to implement intrusion detection systems and to perform deep packet inspection tasks.
A CAM device can be instructed to compare a selected portion of an incoming packet with CAM words stored in an array within the CAM device. More specifically, a CAM device includes a CAM array having a plurality of CAM cells organized in a number of rows and columns. Each row of CAM cells, which can be used to store a CAM word, is coupled to a corresponding match line that indicates match results for the row. Each column of CAM cells is typically coupled to one or more data lines or data line pairs that can be used to drive data into a selected CAM row during write operations and/or for providing a search key to the CAM rows during compare operations. During a compare operation, the search key (e.g., the comparand word) is provided to the CAM array and compared with the CAM words stored therein. For each CAM word that matches the search key, a corresponding match line is asserted to indicate the match result, which is typically stored in a match latch associated with the matching CAM row. If one or more of the match lines are asserted, a match flag is asserted to indicate the match condition, and a priority encoder determines the match address or index of the highest priority matching (HPM) entry in the CAM array.
FIG. 1 is a block diagram of a typical CAM device. CAM device 100 includes a CAM array 110, an address decoder 120, a comparand register 130, a read/write circuit 140, a priority encoder circuit 150, and match logic 160. CAM array 110 includes any number of rows of CAM cells (not shown for simplicity in FIG. 1), where each row of CAM cells can be configured to store a data word. Further, while CAM array 110 is shown in FIG. 1 as a single CAM array, it may include any number of CAM array blocks that can be independently searched.
One or more instructions and related control signals may be provided to CAM device 100 from an instruction decoder (not shown for simplicity) to control read, write, compare, and other operations for CAM device 100. Other well-known signals that can be provided to CAM device 100, such as enable signals, clock signals, and power connections, are not shown for simplicity. Further, although not shown in FIG. 1, each row of CAM cells in CAM array 110 may have one or more validity bits to indicate whether the corresponding row (or any segment thereof) of CAM cells stores valid data.
Each row of CAM cells (not shown in FIG. 1 for simplicity) in CAM array 110 is coupled to address decoder 120 via a corresponding word line WL, and to match latches 112, to priority encoder 150, and to well-known match logic 160 via a corresponding match line ML. For simplicity, the word lines and match lines are represented collectively in FIG. 1. Address decoder 120 is well-known, and includes circuitry to select corresponding rows in CAM array 110 for read, write, and/or other operations in response to an address received from an address bus ABUS using the word lines WL. For other embodiments, addresses may be provided to address decoder 120 from another suitable bus and/or circuitry.
The match lines ML provide match results for compare operations between comparand data (e.g., a search key) and data stored in CAM array 110. Priority encoder 150, which is well-known, uses the match results indicated on the match lines and latches in the match latches 112 to determine the matching entry that has the highest priority number associated with it and generates the index or address of this highest priority match (HPM). In addition, priority encoder 150 may use the validity bits from CAM array 110 to generate the next free address that is available in CAM array 110 for storing new data. Although not shown in FIG. 1, for some embodiments, priority encoder 150 may provide the next free address to the address decoder 120.
Match logic 160, which is well-known, uses the match results indicated on the match lines to generate a match flag indicative of a match condition in CAM array 110. If there is more than one matching entry in CAM array 110, match logic 160 may generate a multiple match flag to indicate a multiple match condition. In addition, match logic 160 may use the validity bits from CAM array 110 to assert a full flag when all of the rows of CAM cells in CAM array 110 are filled with valid entries.
Each column of CAM cells (not shown in FIG. 1 for simplicity) in CAM array 110 is coupled to comparand register 130 via one or more corresponding comparand lines CL, and is coupled to read/write circuit 140 via one or more corresponding bit lines BL. For simplicity, the comparand lines CL and bit lines BL are represented collectively in FIG. 1. Comparand register 130 is well-known, and is configured to provide a search key (e.g., a comparand word) received from a comparand bus CBUS to CAM array 110 during compare operations with data stored therein. For other embodiments, the search key can be provided to CAM array 110 via another bus and/or circuit. Read/write circuit 140 includes well-known write drivers to write data received from a data bus DBUS to CAM array 110 via the bit lines, and includes well-known sense amplifiers to read data from CAM array 110 onto DBUS. For other embodiments, read/write circuit 140 may be coupled to a bus other than DBUS. Further, although not shown in FIG. 1 for simplicity, CAM device 100 can include a well-known global mask circuit (e.g., coupled to the comparand register 130) that can selectively mask the bits of the search key provided to the CAM array 110.
FIG. 2 is a more detailed block diagram of the CAM array 110 of FIG. 1. CAM array 110 is shown to include a plurality of CAM cells 202 organized in any number of rows and columns. The CAM cells 202 can be any suitable type of CAM cell including, for example, binary CAM cells, ternary CAM cells, and/or quaternary CAM cells. As noted above, each row of CAM array 110 may also include one or more validity bits. Each row of CAM cells 202 is coupled to a match line ML and to a word line WL. Each word line WL is driven by address decoder 120 (see also FIG. 1) to select one or more rows of CAM cells 202 for writing or reading. Each match line ML is coupled to priority encoder 150 via a corresponding match latch 212, which together form the match latches 112 of FIG. 1. Each column of CAM cells 202 in CAM array 110 is coupled to read/write circuit 140 via a complementary bit line pair BL/BLB, and to comparand register 130 via a complementary comparand line pair CL/CLB.
Prior to compare operations, the match lines are pre-charged (e.g., to logic high), and each set of complementary comparand line pairs CL/CLB are driven to the same predetermined logic level (e.g., to logic high). Then, during compare operations, the comparand register provides the search key (i.e., the comparand word) to the CAM cells 202 by driving each pair of complementary comparand lines CL/CLB to opposite logic states indicative of the corresponding bit of the search key. For example, to provide a logic low comparand bit to a column of CAM cells, the corresponding comparand line CL is driven to a first logic state (e.g., logic low) and the corresponding complementary comparand line CLB is driven to a second logic state (e.g., logic high); conversely, to provide a logic high comparand bit to the column of CAM cells, the corresponding comparand line CL is driven to the second logic state (e.g., logic high) and the corresponding complementary comparand line CLB is driven to the first logic state (e.g., logic low). Thereafter, if all the CAM cells 202 in a particular row match the corresponding bits of the search key, then the match line ML remains in its logic high state to indicate the match condition. Conversely, if one or more of the CAM cells 202 in the row do not match the corresponding bit of the search key, then mismatching CAM cells 202 discharge the match line (e.g., to ground potential) to indicate the mismatch condition.
Because at least one of each comparand line pair CL/CLB in the CAM array 110 is charged and discharged for every compare operation, power consumption associated with charging and discharging the comparand lines can be significant. Accordingly, there is a need to minimize the power consumption associated with the pre-charging and discharging of the comparand lines in CAM arrays.
Like reference numerals refer to corresponding parts throughout the drawing figures.